%!TeX document-id = {ff202395-b098-4bc3-9327-f6d40065422a}
%!TEX TXS-program:compile = txs:///xelatex/[--shell-escape]
%!TEX encoding = UTF-8 Unicode
\documentclass{lsbook}

\tcbuselibrary{listings}

\title{机器学习笔记}
\DedicatedTo{需要一个书籍模板的人}
%\subtitle{这里可以放一个副标题}
\author{逃课的人工智能}% 默认值
%\BookSeries{计算机应用技术丛书}% 可取消
%\BookIntroduction{这个图书模板是在群主网站上的一个封面模板的基础上改写而成的，设定了一些图书出版要素，设计了封面、扉页及版权页和封底的样式，修改了chapter的样式，并提供了几个选项可切换色彩风格，其余则维持book基本文档类的设定。\par 图书模板部分代码的完成得到了林莲枝大神的帮助，在此表示感谢。由于作者水平有限，模板代码编写不恰当之处还请用户提出批评和指正。\par 感谢造字工坊提供了刻宋、郎宋和黄金时代三种非商业可免费下载使用的字体。\par 感谢谷歌提供自由使用的思源宋体、思源黑体。\par 感谢文泉驿提供的开源的文泉驿等宽微米黑字体。}
\Publisher{平凡之路}
%\Designer{张三丰}
%\Editor{张三丰}
%\edition{2}% 可取消
%\Price{26.5}
%\isbn{978-80-7340-097-2}

%自己所有的设置都放到settings.tex里面
\input{settings.tex}
\begin{document}
\maketitle
\makeflypage
\frontmatter
\tableofcontents

\mainmatter
\chapter{机器学习问题概述}
机器学习旨在寻找一种映射关系，这种映射关系先要拟合每个样本，即特殊化过程，又要在特殊化的过程中寻找一种泛化的形式，好的机器学习模型泛化程度也很高。
\\
从机器学习的任务来看，一般分为三种模型：
\begin{itemize}
\item 回归：输出为实数，$y = f\left( x \right)$。
\item 分类：输出为标签，可以用整数代替，本质还是一种映射。
\item 聚类：相似于分类，输出同样为标签，只是与分类相比在训练时没有标注而已，即没有$y$值。
\end{itemize}

前两类模型是在拟合，而聚类模型更倾向于“解释”，用映射关系去“解释”当前数据集的分布。

\section{损失函数}
损失函数的概念只适用于回归和分类问题。
\newline
损失函数是模型建立的基石，只要找到合适的损失函数，就找到了一条寻找映射关系的路径。机器学习中常见的损失函数有以下几种：
\begin{itemize}
\item 平方和损失：采用的模型有线性回归模型。
\item 指数损失：Adaboost模型即采用的指数损失。
\item 对数损失：一般用于分类模型的损失函数
\item 绝对值损失：可以作为平方和损失的另一种方案。
\end{itemize}

\subsection{平方和损失}
函数形式为：
\begin{align}
L\left( {{Y_i},f\left( {{X_i}} \right)} \right) = \sum\limits_{i = 1}^n {{{\left( {{Y_i} - f\left( {{X_i}} \right)} \right)}^2}}
\end{align}
其中$n$表示样本个数，$Y_i$，$X_i$分别为样本标签值于样本的特征向量，这里的特征向量是指由一个样本所有属性值组成的向量。
如图\ref{pingfanghesuanshi}所示为训练参数为两个的情况下，整个参数空间对应的损失函数值，当然真实的参数空间往往是高维的。这里只是想从更直观的形式给出平方和损失函数的样子。

\begin{figure}
  \centering
  \includegraphics[width=.8\textwidth]{pingfanghesuanshi.png} 
  \caption{平方和损失函数}
  \label{pingfanghesuanshi} 
\end{figure}

使用平方和损失函数进行训练的过程就是在图\ref{pingfanghesuanshi}中根据样本集的分布找到使$z$值最小的参数组合。

\subsection{求解方法}
直接求解法：\newline
梯度下降求解法：批量梯度下降，随机梯度下降，随机平均梯度下降，共轭梯度下降


奇异值分解：


\subsection{对数损失函数}
对数损失函数也可称为对数似然函数，由逻辑回归模型给出，也成为交叉熵损失函数，同时也作为部分人工神经网络的损失函数，如卷积神经网络(CNN)。
这个函数的特性就是可以计算分类这种不连续值的损失。这种特性就是建立在用概率值去表示分类这一基础之上的。
\begin{align}\label{duishusunshihanshu}
- \frac{1}{N}\sum\limits_{i = 1}^N {\sum\limits_{j = 1}^M {{y_{ij}}\log ({p_{ij}})} }
\end{align}
其中$N$表示样本的个数，$M$表示类别的个数，$y_{ij}$是一个二值指标，表示训练集中当前样本$i$是否属于类别$j$，属于等于$1$，不属于为$0$，$p_{ij}$为模型或者分类器对当前样本应用分类$j$的一组参数进行计算得到的概率值。
显然当$M=2$时即为逻辑回归模型的损失函数。

当然你也可以构建自己的损失函数。

\section{过拟合与欠拟合}
在说明过拟合与欠拟合之前，先引入方差与偏差的概念。
方差与偏差的关系就是准与确，偏差量化准，方差量化确。
造成偏差的原因：模型不够准确，不能很好的体现自变量与因变量的关系，怎样改善增加模型的复杂度。
造成方差的原因：自变量和因变量的关系得到了充分表达，自变量细微的变化都可以被模型捕捉到，导致因变量的值比较分散，改善的方法是降低模型复杂度。
求平均可以降低偏差，决策树的剪纸可以降低方差。


从上面的描述中可以总结，过拟合就是低偏差，高方差；欠拟合是高偏差，低方差。
减少过拟合就是要降低训练集对模型的影响，方法有：
\begin{enumerate}
\item 数据扩增，扩增的根据是加入更多情况，更多干扰。人为增加数据量，可以用增加随机噪声、GAN、图像数据的空间变换（平移旋转镜像）、尺度变换（缩放裁剪）、颜色变换、增加噪声、改变分辨率、对比度、亮度等。其中增加噪声，可以在原始数据上直接加入随机噪声（更接近真实环境），也可以在权重上增加噪声。
\item 直接降低模型复杂度，正则化权值，提前停止训练（奥坎姆剃刀原则），即减少模型参数数量。例如：对于LR，减少目标函数的因子数；对于DT，减少树的深度、剪枝等；对于DNN，减少层数和每层权向量长度。
\item 针对神经网络，采用dropout方法，依据还是消弱训练集的影响，降低模型复杂度。（有待讨论）
\item 多模型投票方法，集成学习。降低单个模型对预测结果的影响。
\item 贝叶斯方法（未理解），贝叶斯方法本质上就是一个平均，平滑（averaging），这里我们只考虑了单层的贝叶斯模型，实际上，贝叶斯方法在多层的超参数存在时照样十分自然优美，不过是多几重积分而已。通过平均，融合了不同的可能性，使得预测结果更加稳定。其实线性回归并不是贝叶斯方法最常用的地方，而是自然语言处理中的语言模型里的 add-x smoothing（加x平滑），所谓加x平滑实际上是 multinomial 分布加上狄利克雷先验后的预测分布。
\end{enumerate}

欠拟合就是提高训练集对模型的影响，最简单的方法就是增加模型的复杂度。

\section{归一化，正则化与标准化}
\subsection{归一化}
\begin{enumerate}
\item 把数据变为$(0，1)$之间的小数。主要是为了方便数据处理，因为将数据映射到0～1范围之内，可以使处理过程更加便捷、快速。
\item 把有量纲表达式变换为无量纲表达式，成为纯量。经过归一化处理的数据，处于同一数量级，可以消除指标之间的量纲和量纲单位的影响，提高不同数据指标之间的可比性。
\end{enumerate}
主要算法：
\begin{enumerate}
\item 线性转换，即min-max归一化（常用方法）。$y=\frac{(x-min)}{(max-min)}$
\item 对数函数转换。$y=log_{10}(x)$
\item 反余切函数转换。$y=atan(x)\frac2\pi$
\end{enumerate}   
归一化会将数据集汇聚于一个区域，如果数据集中有异常点，归一化之前可能正常数据与异常数据相隔较远，但是归一化之后异常数据和正常数据都聚集在$(0,1)$区间中。     
\subsection{正则化}
通过数据集拟合出来的对应关系有很多种，使用正则化可以从这些对应关系中挑选出一组简单的（系数值符合正则要求）对应关系。
\subsection{标准化}
数据的标准化是将数据按比例缩放，使之落入一个小的特定区间。主要方法：
\begin{enumerate}
\item z-score标准化，即零-均值标准化（常用方法）$y=\frac{(x-μ)}σ$是一种统计的处理，基于正态分布的假设，将数据变换为均值为0、标准差为1的标准正态分布。但即使数据不服从正态分布，也可以用此法。特别适用于数据的最大值和最小值未知，或存在孤立点。
\item 小数定标标准化$y=\frac{x}{10^j}$（$j$确保$max(|y|)<1$）通过移动$x$的小数位置进行标准化。
\item 对数Logistic模式，$y=\frac{1}{(1+e^{(-x)})}$。
\end{enumerate}
标准化是在不改变数据集分布的前提下缩放数据，数据集中的异常点仍旧离正常点较远。
\section{一些评价标准介绍}
这些评价标准一般分为，精确率，召回率，ROC曲线，F1值，用于评价翻译对话系统的BELU等指标。
\subsection{精确率与召回率}
精确率表示的是在预测为正的样本中，预测对的占比多少；召回率表示预测为正的样本个数占真实的总的正例样本个数的比例。
以从一个装有红球和黑球的盒子里随机抓一把球为例，假设黑球为正，红球为负。这随机一把球中的黑球个数比上这一把球的总个数为精确率；黑球个数闭上盒子里总的黑球个数为召回率。

\subsection{ROC曲线以及F1值}
还以黑球和红球的为例；ROC曲线是以真正率及召回率为纵坐标，以假正率（盒子中总的黑球个数减去随机一把中的黑球个数然后再比上盒子中红球的个数）为横坐标。模型的输出一般以
概率值的形式表示，通过设置不同的阈值，将大于该阈值的设置为正例，小于该阈值的为负例，设置不同的阈值可以计算出不同的召回率和假正率，就可以绘制成ROC曲线，有了ROC曲线就可以计算曲线下面的
面积AUC，计算的方法采用梯形近似计算。


F1值的公式可以表示为:
\begin{align}
F1 = 2\bullet\frac{precision \bullet recal}{precision+recal}
\end{align}

\subsection{准确率}
准确率（Accuracy）衡量的是分类正确的比例。设$y^i$是是第$i$个样本预测类别，$y_i$是真是类别，在nsample个测试样本上的准确率为：
\begin{align}
accuracy=\frac1{nsample}\sum_{i=1}^{nsample}1{(y^i=y+i)}。
\end{align}
其中$1(x)$是indicator function，当预测结果与真实情况完全相符时准确率为$1$，两者越不相符时为$0$。
虽然准确率适用范围很广，可用于多分类以及多标签等问题上，但在多标签问题上很严格，在有些情况下区分度较差。

\chapter{回归模型}
%目前颜色选择共三种，\texttt{green}，\texttt{orange}和\texttt{violet}，默认为\texttt{green}。你也可以自己设置 \texttt{cvprimary}, \texttt{cvsecondary} 以及 \texttt{cvtext}，定制你自己喜欢的色盘。
回归模型有线性回归、逻辑回归
\section{线性回归}
映射关系：
\begin{align}
\begin{array}{l}
y = {\theta _1}{x_1} + {\theta _2}{x_2} + {\theta _3}{x_3} + {\theta _4}{x_4} +  \cdots \\
y = {\theta _1}{x_1}{x_2} + {\theta _2}x_2^2 + {\theta _3}{x_3} + {\theta _4}{x_4} +  \cdots 
\end{array}
\end{align}
上式中${x_1}$、${x_2}$的组合形式是根据样本集而定的，这里只给出其中的两种组合方式。线性回归模型的训练目的就是找到上述形式的映射关系。
找到上述映射关系的途径就是使下式（平方和损失函数）的值达到最小：
\begin{align}\label{zuixiaoercheng}
J\left( \theta  \right) = \frac{1}{2}\sum\limits_{i = 1}^m {{{\left( {{h_\theta }\left( {{x^i}} \right) - {y^i}} \right)}^2}} 
\end{align}
上式的证明基于一个前提，即误差是独立同分布的，且服从均值为0，方差为某定值${\sigma}^2$的高斯分布。这一点可以通过中心极限定理推出，


证明：
首先我们有式：
\begin{align}
y^i=\theta^Tx^i+{\varepsilon}^i
\end{align}
其中${\varepsilon}^i$服从标准正态分布，即：
\begin{align}
P({\varepsilon ^i}) = \frac{1}{{\sigma \sqrt {2\pi } }}{e^{ - \frac{{{{({\varepsilon ^i})}^2}}}{{2{\sigma ^2}}}}}
\end{align}
引入似然函数，
\begin{align}
L(\theta ) = \prod\limits_{i = 1}^m {P({\varepsilon ^i})}
\end{align}

然后使似然函数值达到最大，关于使似然函数值达到最大的说明是：存在即合理，我们现在有一个样本集合，需要拟合出一个函数，使似然函数最大就是，找到一个最大可能产生这个样本集的函数（映射关系），
这一点内在的体现了“拟合”。由于在求最大似然函数的过程中连乘显然对于求导来说是复杂的，因此通过对似然函数求对数，可以将连乘变为求和，求和式对于求导是简单的。
将上述似然函数求对数然后取极大值，很容易的得到\cref{zuixiaoercheng}。


有了损失函数就可以开始训练以获得最优模型参数。

\begin{framed}
拓展1:林德伯格-莱维中心极限定理
设${X_n}$是独立同分布的随机变量序列，且$E(X_i)=\mu, Var(X_i)={\sigma}^2>0$存在，若记\\
\begin{align}
Y_n^* = \frac{{{X_1} + {X_2} +  \cdots  + {X_n} - n\mu }}{{\sigma \sqrt n }}
\end{align}
则对任意实数$y$，有
\begin{align}
\mathop {\lim }\limits_{n \to \infty } P\left( {Y_n^* \le y} \right) = \Phi \left( y \right) = \frac{1}{{\sqrt {2\pi } }}\int_{ - \infty }^y {{e^{ - \frac{{{t^2}}}{2}}}dt}
\end{align}

中心极限定理表明一个随机变量如果是由大量微小的、独立的随机因素的叠加结果，那么这个变量一般都可以认为服从正态分布。


拓展2：似然函数与概率的区别


概率描述了已知参数时的随机变量的输出结果；似然则用来描述已知随机变量输出结果时，未知参数的可能取值。
\end{framed}
\section{局部加权回归}
局部加权回归模型的构建依据是：以离当前点的距离的倒数为权值，作用于回归模型的损失函数，以此来消弱远距离点对当前点的影响和增加距离近的点对当前点的作用来实现局部线性回归。
局部线性回归模型擅长捕捉数据集细微的特征，但是容易造成过拟合。

\section{逻辑回归}
逻辑回归模型虽然叫回归，但是其主要用于分类。逻辑回归可以归结为针对一个二分类问题训练一组参数。
考虑怎样使用回归的方法处理分类问题，回归最后的输出一般都是实数，而分类问题只有两个输出，要么是正标签，要么是负标签。所以为了能用回归的方法训练分类模型，需要找到一个从实数到
两种标签的映射关系。


逻辑回归中经常采用sigmod函数来实现这种映射，图\ref{sigmod}很好的描述了上述性质，从样本属性值到概率值是通过sigmod函数，然后从sigmod函数值到分类利用简单规则，大于0.5的属于一类，小于0.5的属于另一类。

\begin{figure}
  \centering
  \includegraphics[width=.8\textwidth]{sigmod.png} 
  \caption{Sigmod函数}
  \label{sigmod} 
\end{figure}

解决了用回归表示分类的问题，剩下的就可以使用在线性回归中的方式构建损失函数，并通过使损失函数达到最小而建立最优模型。
这里直接给出逻辑回归的似然函数以及损失函数：

此外逻辑回归不但可以进行分类，还可以给出所属分类的概率。
\newline
上述模型由于最后输出是两个标签，所以只能使用于二分类，为了向单标签多分类扩展，需要对模型进行修改，对于多分类问题，假设分类标签有A,B,C三种，为了使用逻辑回归，只需要简单的将样本集标签分为A、非A，
然后使用逻辑回归训练一组参数，然后再将样本集标签分为B，非B，再训练一组参数，对C类也做同样处理，这样就处理了多分类问题，我们将这个模型称为SoftMax模型。
SoftMax的映射为，从样本属性值到一组概率值得映射，这个映射关系为：
\begin{align}
P\left( x \right) = \frac{{{e^{\theta _k^Tx}}}}{{\sum\limits_{l = 1}^K {{e^{\theta _l^Tx}}} }},k = 1,2, \cdots K
\end{align}
然后取映射后的一组概率值中最大的作为分类结果。

\chapter{分类模型}
对于分类模型，我将其分为两类，一类是采用一种机制，这种机制强调的是一种做法、玩法，没有完美的数学理论去支撑，例如KNN，密度聚类，谱聚类，层次聚类等；另外一种是完全基于数学理论推导出来的。当然两种算法的优缺点也是很明显的。
第一种实现简单，搭配合适的参数也能做到很好的效果；第二种模型复杂，但是有足够的理论支撑，个人比较倾向于第二种模型。
\section{KNN}
KNN的思想很简单，就是拿着测试样本与训练样本进行比较，实现给定$K$值，如果与测试样本点距离最近的点的个数超过了$K$值，就将当前样本归为这一类。
对于样本数量较少时可以直接使用暴力的方式计算最近邻，但是如果样本量很大时这种暴力的方式显然是不可取的因此寻找一种方法能快速的找到最近邻点，KD-tree就是为了解决这一问题提出的。
KNN模型的关键在于KD-tree的构建，KD-tree是一种数据结构，在这种数据结构之下能很容易的进行寻找最近邻点的操作。因此接下来我们讨论怎样构建KD-tree。


采用方差进行划分的原因是：方差大代表数据的波动越大，取中值操作可以很好的将样本集分开，这个操作就比如切黄瓜，竖着切不好操作，而横着切很容易就把黄瓜分成两瓣。

\begin{tcblisting}{listing only,applelight,title={KD-Tree伪码},
  listing options={basicstyle=\ttfamily,columns=fullflexible,
  language={[LaTeX]TeX},moretexcs={colorlet,definecolor,PassOptionsToPackage}}
}

#KD-tree的非叶子节点只保存的是空间划分信息（比如划分维度，划分值等），真正的数据都保存在叶子节点中。
class Node():
    pass

def createKDTree(dataSet, parentNode):

    tempNode = Node()
    
    #leefNodeNum表示叶子节点中样本点的个数
    if len(dataSet)==leefNodeNum:
        tempNode.data = dataset
        tempNode.parent = parentNode
        return tempNode
        
    indexFeatrue = 获取dataset中方差最大的特征属性
    midnum = 该特征属性取值的中位数
    tempNode.indexFeatrue = indexFeatrue
    tempNode.midnum = midnum
    
    leftData = []
    rigthDta = []
    for tempData in dataset:
        if tempData[indexFeatrue]<midnum:
            leftData.append(tempData)
        else:
            rigthDta.append(tempData)
    
    tempNode.left = createKDTree(leftData, tempNode)
    tempNode.right = createKDTree(rigthDta, tempNode)
    
    #为了回溯操作添加父节点
    tempNode.parent = parentNode
    
    return tempNode
    
\end{tcblisting}


\begin{tcblisting}{listing only,applelight,title={利用KD-tree进行近邻查找算法伪码},
  listing options={basicstyle=\ttfamily,columns=fullflexible,
  language={[LaTeX]TeX},moretexcs={colorlet,definecolor,PassOptionsToPackage}}
}

def getKnn(Node, onceData):

    if Node.midnum==null:
        for tempData in Node.data:
            找出Node.data中tempData的K个紧邻样本点。
        if 找出的样本点个数不够K个，则需要进行回溯操作
        
        if 使用距离r值来查找最近邻点，而使用r值和tempdata构建的超球面与同层包含另一个
            子节点的超巨形相交时，也需要进行回溯。
        
        为了进行回溯操作的方便在构建KD-tree时在每个非叶子节点添加两种数据：
        第一种是记录下每一个子树中包括的全部数据在该子树相应的维度k上的边界參数[min, max]大于最小值，
        小于最大值就有交线；另外一种是记录下每一个子树所在的切割维度k和切割值m，
        切割值m就是中值(k,m)。被检测样本点与子树的距离则为|Q(k) - m|，Q(k)为样本点第k维特征属性的值。
        
        return 包含K个进邻点的列表
        
    
    if oncedata<Node.midnum:
        getKnn(Node.left, onceData)
    else:
        getKnn(Node.right, onceData)

    
\end{tcblisting}

\section{决策树}
首先，在了解树模型之前，自然想到树模型和线性模型有什么区别呢？其中最重要的是，树形模型是一个一个特征进行处理，之前线性模型是所有特征给予权重相加得到一个新的值。
决策树与逻辑回归的分类区别也在于此，逻辑回归是将所有特征变换为概率后，通过大于某一概率阈值的划分为一类，小于某一概率阈值的为另一类；而决策树是遍历每一个特征，每个特征的不同的分法（回归树）/不同的标签分类(分类树)来做划分。
另外逻辑回归只能找到线性分割（本质上是线性的，只不过引入了一个非线性函数来处理不能线性可分的情景），而决策树本质上就是一个非线性分割，来表示析取的合取这种关系。

构建决策树模型需要注意以下几点：
\begin{itemize}
\item 依据什么构建决策树


在解决这个问题之前需要引入几个新的概念：


第一个是信息熵，表达如下式。信息熵是消除不确定性所需信息量的度量，也即未知事件可能含有的信息量。我们一般知道事件发生的概率，需要构建由概率衡量信息量的方法，$log$函数是一个不错的选择，至于为什么选以$2$为底是因为方便比特化。

\begin{align}\label{xinxiliang}
H\left( X \right) =  - \sum\limits_{i = 1}^m {{p_i}{{\log }_2}({p_i})}
\end{align}
下面给出上式（可以看做$-log_2(p_i)$的期望）的由来：考虑两个不相关的事件X和Y，这两个事件同时发生的信息量等于各自发生时获取的信息量之和，即：
\begin{align}\label{xinxiliangxiangjia}
H(x,y)=H(x)+H(y)
\end{align}
\cref{xinxiliang}表示的是信息量和概率的关系，两个独立事件的概率为：
\begin{align}\label{xinxilianggailv}
P(x,y)=P(x)P(y)
\end{align}
为了建立信息量与概率之间的关系，需要找到一个表达式符合\cref{xinxilianggailv}和\cref{xinxiliangxiangjia}性质，即对两个变量相加做变换等于分别对两个变量先做变换再相乘。
对数变换很好的满足了这一性质，因此我们构建\cref{xinxiliang}，正好符合上述性质。

有时候需要求在事件A发生的前提下事件B的信息熵，因此引入条件熵的定义：
\begin{align}
H\left( {X|Y} \right) = H(X,Y) - H(X)
\end{align}
第二个概念是：基尼系数，定义如下：
\begin{align}
Gini(p) = \sum\limits_{k=1}^{K}p_k(1-p_k) = 1- \sum\limits_{k=1}^{K}p_k^2
\end{align}
对于个给定的样本D，$|D|$表示样本数量。假设有k个类别, 第k个类别的数量为$C_k$,则样本$D$的基尼系数表达式为：
\begin{align}
Gini(D) = 1-\sum\limits_{k=1}^{K}(\frac{|C_k|}{|D|})^2
\end{align}

第三个概念是错误率：
\begin{align}
Error = 1 - \max \{ p(i)\}
\end{align}
上式中$p(i)$表示事件$i$的概率。


三个概念的关系如图\ref{xinxishangGinixishu}所示，三个公式的值越大，表示数据越不纯，越小表示越纯。
\begin{figure}
  \centering
  \includegraphics[width=.8\textwidth]{xinxishangGinixishu.png} 
  \caption{信息熵，错误率与Gini系数对比}
  \label{xinxishangGinixishu} 
\end{figure}
从图\ref{xinxishangGinixishu}中可以看出，基尼系数，信息熵与ERROR的区别就是斜率不同。
这三个函数都满足一个性质：只要频率中有一个的值很大，整个函数的值就很小，如果，频率都相差没多少的话，这个值就很大。只要两个频率中有一个值很大，代表该事件是常识事件比如“太阳从东方升起”，
所包含的信息量就很少。


上述三个概念就是构建决策树时所依据的指标。
\begin{tcblisting}{listing only,applelight,title={决策树构建伪码},
  listing options={basicstyle=\ttfamily,columns=fullflexible,
  language={[LaTeX]TeX},moretexcs={colorlet,definecolor,PassOptionsToPackage}}
}

#以构建二叉决策树为例，多叉决策树构建方式相似。
class Node():
    pass

def createTree(dataSet):

    tempNode = Node()
    
    #分支结束条件，这里只简单的给出以样本个数为标准的判断
    if len(dataSet)<=叶子结点的样本数：
        tempNode.data = dataset
        return tempNode
    
    resaultList = []
    for onceKey in 样本的属性列表:
        for onceSplit in 对于当前样本属性的一种分割方式 :
            选择一种指标进行计算，并将计算结果添加进指标列表resaultList
     
    选择resaultList列表中最小的作为分割依据
    
    对数据进行分割。
    tempNode.left = createTree(分割后的左子树数据集)
    tempNode.right = createTree(分割后的右子树数据集)
    
    return tempNode  
    
\end{tcblisting}
对于待划分的数据集D，其entroy(前)是一定的，但是划分之后的熵 entroy(后)是不定的，entroy(后)越小说明使用此特征划分得到的子集的不确定性越小（也就是纯度越高），
因此entroy(前)-entroy(后)差异越大，即信息增益度越大，说明使用当前特征划分数据集D的话，其纯度上升的更快。而我们在构建最优的决策树的时候总希望能更快速到达纯度更高的集合，
这一点可以参考优化算法中的梯度下降算法，每一步沿着负梯度方法最小化损失函数的原因就是负梯度方向是函数值减小最快的方向。
同理：在决策树构建的过程中我们总是希望集合往最快到达纯度更高的子集合方向发展，因此我们总是选择使得信息增益最大的特征来划分当前数据集D。

\item 分支结束的条件


条件一：当每个子节点只有一种类型时；

条件二：当前样本点个数小于等于叶子结点允许的样本个数，或者达到迭代次数，伪码中可以使用树的深度来实现。

\end{itemize}

对于判断每个叶子结点的所属的分类一般有两种情况：
\begin{enumerate}
\item 叶子结点中的样本数全为一类
\item 叶子结点中的样本数的类别多于一类，这时取样本集中属于一个类别样本数目最多的作为这个结点的分类，即少数服从多数。
\end{enumerate}

为了防止决策树模型的过拟合，需要对决策树进行剪枝操作。
如果决策树深度越深，叶节点越多，说明决策树对训练数据有充分的表达，但是在测试集上不一定能表现出很好的性能，从而造成过拟合。
剪枝算法的基本思路是：剪去决策树模型中的一些子树或者叶结点，并将其上层的根结点作为新的叶结点，从而减少了叶结点、层数，降低了决策树复杂度。
剪枝算法又分为两种：
\begin{enumerate}
\item 预剪枝
通过提前停止树的构建而对树剪枝。停止决策树生长最简单的方法有：
\begin{enumerate}
\item 定义一个高度，当决策树达到该高度时就停止决策树的生长
\item 达到某个节点的实例具有相同的特征向量，即使这些实例不属于同一类，也可以停止决策树的生长。这个方法对于处理
数据的数据冲突问题比较有效。这个不理解
\item 定义一个阈值，当达到某个节点的实例个数小于阈值时就可以停止决策树的生长
\item 定义一个阈值，通过计算每次扩张对系统性能的增益，并比较增益值与该阈值大小来决定是否停止决策树的生长。再增加树的深度对模型的增益小于阈值，这时候就可以停止决策树的生长
\end{enumerate}

\item 后置剪枝，简单来说就是在决策树构建完成后再进行剪枝。


在介绍后置剪枝前，需要先给出决策树损失函数的量化形式，因为剪枝后的效果是需要损失函数来判断的。决策树的损失函数可以由下式给出：
\begin{align}\label{jueceshusunshihanshu}
C(T) = \sum\limits_{t = 1}^{{T_{{\rm{leaf}}}}} {\frac{{{N_t}}}{N}{H_t}(T)}
\end{align}
\cref{jueceshusunshihanshu}中，${H_t}(T) =  - \sum\limits_{k = 1}^K {\frac{{{N_{tk}}}}{{{N_t}}}\log (\frac{{{N_{tk}}}}{{{N_t}}})} $为$t$叶子结点的信息熵，损失函数可以看做对信息熵以概率$\frac{N_t}{N}$
出现的期望。$t$表示树T的叶结点，${N_t} = \sum\limits_{k = 1}^K {{N_{tk}}}$表示t叶子结点中含有的样本个数，$N_{tk}$表示t样本节点中第k类的样本个数，K为整体样本集的类别种类,$T_{leaf}$为数$T$的叶子结点总数。
现在我们需要对树进行剪枝操作，来寻找一个结构简单，预测效果更好的决策树，结构简单是指叶结点少，层数少，一般层数少是通过叶子结点少体现的，因此主要目的是使叶子结点少，为了满足这个要求，我们需要
修改损失函数，类似于正则化一样，重新构建损失函数如下：
\begin{align}\label{jueceshusunshihanshugegx}
C(T) = \sum\limits_{t = 1}^{{T_{{\rm{leaf}}}}} {\frac{{{N_t}}}{N}{H_t}(T)}  + \alpha {T_{leaf}}
\end{align}
模型在训练过程中会根据$\alpha$的值去寻找叶子结点少，熵更低的参数。评价损失函数即为信息熵的期望，表示整课树的信息熵期望，期望代表的是一个稳定的值，这个稳定值可以很好的表示分类效果。
遵循新构建的损失函数怎么能实现剪枝呢？例如设一个结点r有n个样本，其组成是第i类有$N_i$个样本，假设在分了几个孩子结点后各个叶结点的成分仍保持原比例，即${\frac{{{N_i}}}{N}}$值不变，
记新的子树为R，可以计算得出评价函数$C(r)=C(R)$，因为此时的模型对分类没有任何贡献，浑水依旧还是浑水，在随机分组后不会有任何分类效果的改进，如果没有新增加的项${\alpha} {T_{leaf}}$那么模型训练完成后会输出新的子树R，但是添加项$\alpha {T_{leaf}}$后，
模型为了最小化损失函数的值，会选择输出叶子结点少的树模型，不会再进行分支操作。
讨论$\alpha$对模型影响的时候可以借助于极值法，就是当$\alpha$等于0或者无穷时，对模型训练的影响，很容易讨论，等于0时混乱程度对损失函数的贡献最大，模型训练会侧重于降低模型的混乱程度即信息熵；等于无穷时，叶子结点的
个数占主导地位，模型训练过程会侧重于减少叶子结点的个数，由于$\alpha$为正无穷，所以模型的输出只有一个结点即根节点。


后置剪枝的计算步骤：


如图\ref{jianzhi}$r$表示剪枝后，$R$表示剪枝前。根据\cref{jueceshusunshihanshugegx}给出两个模型的损失函数：
\begin{align}\label{jianzhi1}
\begin{array}{l}
{C_\alpha }({\rm{r}}) = C(r) + \alpha \\
{C_\alpha }(R) = C(R) + {N_R}\alpha 
\end{array}
\end{align}
\cref{jianzhi1}中$N_R$表示子树$R$的叶子结点个数。一般地有$C(r)>c(R)$，因为树结构越复杂信息熵一般越低，为方便理解这里引入一个例子，现在有一盆装有赤橙黄绿青蓝紫七种颜色的糖豆的瓶子，现在使用决策树进行分类，分类的结果就是各种颜色
分为一类，即叶子结点中的元素就是同一种颜色的糖豆，可能加载有其他颜色的糖豆，因为不存在完美模型。对于$C(r)>c(R)$的解释就是，按照分类规则开始分类只会分的越来越清楚，而不是越分越混乱，最不济就是相等。令$C_{\alpha}(r)=C_{\alpha}(R)$，可以求得$\alpha  = \frac{{C(r) - C(R)}}{{{N_R} - 1}}$
单个根节点也是一个树。在构建决策树的时候顺便把每个非叶子结点的$\alpha$计算出来。然后在剪枝阶段，根据$\alpha$从小到大的顺序开始依次删除非叶子结点，直至剩下根节点。然后取损失函数最小的那个决策树作为整个模型的输出。
\end{enumerate}

\begin{figure}
  \centering
  \includegraphics[width=.8\textwidth]{jianzhi.png} 
  \caption{剪枝前后示意图}
  \label{jianzhi} 
\end{figure}

有分类就会很自然的想到回归，是否可以通过决策树模型实现回归，当然是可以的，回归模型要求输出的是一个实数值，为满足这个要求只需要将分类中的叶子结点输出规则（少数服从多数）改为求整个叶子结点所有值得均值即可。
另外，分类树使用的是信息增益率作为构建决策树的方法，回归树中标签值是实数，信息增益率已经失效了，需要采用新的指标，一般采用均方差作为分支依据，均方差表示为：
\begin{align}
MSE = \frac{1}{n}\sum\limits_{i = 1}^N {{{({y_i} - {{\hat y}_i})}^2}}
\end{align}

\section{SVM支持向量机}
支持向量机也可以成为支持向量网络，可以将其看为单层的神经网络，通过核的引入使SVM适合处理非线性分类问题。
\subsection{空间点集的分类问题}
现在我们考虑一个空间点集的分类问题，很容易想到分类平面，但是能将点集分开的分类平面有很多，使用哪个分类平面能最大可能的保证模型的分类可信度。
SVM采用使间隔最大化的方法来达到最大化分类可信度。为了找到这样的分割平面，先引入几个描述分割平面的量。使用$\vec W \cdot \vec x + b = 0 $表示分割平面。
$\vec W$即为该平面的法向量，进而可以给出空间任意一点$\vec {x_i}$关于此分割平面的距离公式：
\begin{align}
\gamma = abs(\frac {\vec W}{|\vec W|} \cdot {\vec {x_i}} + \frac {b}{|\vec W|})
\end{align}
考虑到正负，修改上式引入标签值$y_i$，标签值取值为$1$,或者$-1$，将上式修改为：
\begin{align}
\gamma = y_i(\frac {\vec W}{|\vec W|} \cdot {\vec {x_i}} + \frac {b}{|\vec W|})
\end{align}
有了上述描述，我们可以将空间点集的分类问题数学化为求解以下最优化问题：
\begin{align}
max: \gamma
s.t.: y_i(\frac {\vec W}{|\vec W|} \cdot {\vec {x_i}} + \frac {b}{|\vec W|}) > \gamma, i \in (1,2,\cdots, N)
\end{align}
对于上式中$y_i(\frac {\vec W}{|\vec W|} \cdot {\vec {x_i}} + \frac {b}{|\vec W|})$正辩于$y_i({\vec W} \cdot {\vec {x_i}} + b)$，我们将此式称为函数距离，
可以看出函数距离的大小对最优化问题的条件不产生影响，因此可以令函数距离等于$1$，简化最优化问题为：
\begin{align}
min: \gamma = \frac {1}{2}{|\vec W|}^2
s.t.: {y_i}(\vec W\overrightarrow {{x_i}}  + b) - 1 > 0,i \in (1,2, \cdots ,N)
\end{align}
对于带有条件的最优化问题一般通过写成拉格朗日表达式的方法来求解，拉格朗日方法可以将目标函数与条件表达式用一个式子表示，变为无约束优化问题来进行求解，这样就可以通过求解拉格朗日表达式的
最优化来求解原始问题。对于本问题的拉格朗日表达式为：
\begin{align}
L(w,b,\alpha) = \frac{1}{2}{|\vec w|}^2-\sum_{i=1}^N{{\alpha}_iy_i(\vec w \cdot x_i + b)} + \sum_{i=1}^N{\alpha_i}
\end{align}
上式中${\alpha}_i$为拉格朗日乘子。


在有些拉格朗日表达式给定的条件下，直接进行求导最优化可能不方便计算，例如SVM中的如果对权值进行求导，需要考虑权值的每个维度，这样计算起来比较复杂，通过构建当前
问题的对偶问题来进行求解，将原始问题中的复杂参数用简单参数代替，例如SVM中的用$\alpha_i$表示$\vec W$，因为$\alpha_i$只与样本的个数相关，这样就可以将原始问题转化为只和$\alpha$相关的最优化问题，
条件表达式也由原始的不等变为等式，并且对于SVM来说更容易引入核函数。关于详细的SVM对偶问题的证明请参考《统计学习方法》一书，这里不再给出详细推导，只给出思路。
原始问题的对偶问题可以描述为下式：
\begin{align}\label{SVM01}
\begin{array}{l}
\mathop {\min }\limits_\alpha  {\rm{ }}\frac{1}{2}\sum\limits_{i = 1}^N {\sum\limits_{j = 1}^N {{\alpha _i}{\alpha _j}{y_i}{y_j}\left( {{x_i}{x_j}} \right) - \sum\limits_{i = 1}^N {{\alpha _i}} } } \\
s.t.{\rm{   }}\sum\limits_{i = 1}^N {{\alpha _i}{y_i}}  = 0
\end{array}
\end{align}
\subsection{SMO}
对于\cref{SVM01}，可以采用SMO算法来进行求解。SMO算法的依据是可以将整个问题拆解为多个子问题，通过求解满足每个子问题的最优化解来给出原始问题的最优解。
\subsection{核函数}
\cref{SVM01}存在${{x_i}\cdot{x_j}}$就可以看作为一个核函数，只不过此时的核函数为$K(x_i,x_j)={{x_i}\cdot{x_j}}$，当然也可以引入其他核函数，例如多项式核，高斯核等。
核函数的引入让我们摆脱了寻找从空间之间的映射关系，而是直接定义一个核函数。这里存在一个问题，是不是可以将任何函数当作核函数？需要更深一步的讨论。




\section{集成学习}
常见的集成学习框架有：
\begin{enumerate}
\item Bagging，随机森林
\item Boosting，Adaboost、GBDT
\item Stacking
\end{enumerate}

集成学习的模型一般表示为一个模型集合，通过集合一组弱分类器的模型，来构建一个强分类器。对于数据集过大或者过小，可以采用有放回的操作产生不同的数据
子集，然后使用数据子集训练不同的分类器，最终再合并成为一个大的分类器；如果数据的划分边界过于复杂，使用线性模型很难描述情况，那么可以训练多
个模型，然后再进行模型的融合；对于多个异构的特征集的时候，很难进行融合，那么可以考虑每个数据集构建
一个分类模型，然后将多个模型融合。以上就是集成学习的优点。
\subsection{Bagging}
Bagging方法又叫做自举汇聚法(Bootstrap Aggregating)，思想是：在原始数
据集上通过有放回的抽样的方式，重新选择出S个新数据集来分别训练S个分类器
的集成技术。也就是说这些模型的训练数据中允许存在重复数据。Bagging方法训练出来的模型在预测新样本分类的时候，会使用多数投票或者求
均值的方式来统计最终的分类结果。多数投票对应于分类，求均值对应于预测值。Bagging方式是有放回的抽样，并且每个子集的样本数量必须和原始样本
数量一致，但是子集中允许存在重复数据。
\begin{enumerate}
\item 随机森林（RF）


随机森林是一种Bagging模型，主要关注于两个随机：有放回随机抽取n个样本，允许重复，n为总的样本个数；随机选取k个属性。
然后在这个基础上构建模型，或是决策树，或者是其他基础模型，组成多个基础模型组合，称之为随机森林。
随机森林有几个推广算法：
\item Extra Tree 


与RF相比，Extra Tree每个基本模型都会采用原始数据；在构建决策树挑选分割点时，Extra tree只是随机的挑选一个特征值来划分决策树。
因为Extra tree是随机挑选一个特征值进行划分，因此这个模型的泛化能力比RF强。在模型构造过程中加入随机因素可以增强模型的泛化能力。
\item Totally Random Trees Embedding(TRTE) 


TRTE主要用于将低维数据映射到高维数据，映射的方法为：


TRTE算法的转换过程类似RF算法的方法，建立T个决策树来拟合数据。当决策
树构建完成后，数据集里的每个数据在T个决策树中叶子节点的位置就定下来了，
将位置信息转换为向量就完成了特征转换操作。案例：有3棵决策树，每棵决策树有5个叶子节点，某个数据x划分到第一个决策
树的第3个叶子节点，第二个决策树的第一个叶子节点，第三个决策树的第第五
个叶子节点，那么最终的x映射特征编码为:(0,0,1,0,0, 1,0,0,0,0, 0,0,0,0,1)。
\item Isolation Forest 


IForest是一种异常点检测算法，样本集当中的异常点因为比较特殊所以一般比较好分类，识别。在决策树的浅层就可以被分到叶子结点。该模型就是基于这个性质完成异常点检测。
IForest算法会随机选择一个划分特征，并对划分特征随机选择一个划分阈值，与RF相比在构建决策树过程中更随机。对于异常点的判断，则是将测试样本x拟合到T棵决策树上。计算在每棵树上该
样本的叶子节点的深度$h_t(x)$。从而计算出平均深度$h(x)$；然后就可以使用下列公
式计算样本点x的异常概率值，$p(s,m)$的取值范围为[0,1]，越接近于1，则是异常
点的概率越大，其中$p(s,m)$定义为：

\begin{align}\label{iforest}
p(x,m) = {2^{ - \frac{{h(x)}}{{c(m)}}}}
\end{align}
\cref{iforest}中，$c(m)=2ln(m-1)+\xi-2{\frac{{m - 1}}{m}}$，$m$位样本个数，$\xi$为欧拉常数（调和级数与自然对数的差值的极限）。
\end{enumerate}

\subsection{Boosting}
提升学习（Boosting）是一种机器学习技术，可以用于回归和分类的问
题，它每一步产生弱预测模型(如决策树)，并加权累加到总模型中；如果
每一步的弱预测模型的生成都是依据损失函数的梯度方式的，那么就称
为梯度提升(Gradient boosting)；提升技术的意义：如果一个问题存在弱预测模型，那么可以通过提升技
术的办法得到一个强预测模型；

\begin{enumerate}
\item Adaboost


Adaboost是一种迭代算法。每轮迭代中会在训练集上产生一
个新的学习器，然后使用该学习器对所有样本进行预测，以评估每个样
本的重要性。换句话来讲就是，算法/子模型会为每个样本
赋予一个权重，每次用训练好的学习器标注/预测各个样本(训练数据)，
如果某个样本点被预测的越正确，则将样本权重降低；否则提高样本的
权重。权重越高的样本在下一个迭代训练中所占的权重就越大，也就是
说越难区分的样本在训练过程中会变得越重要；整个迭代过程直到错误率足够小或者达到一定的迭代次数为止。
Adaboost具有聚焦机制，它会对特别关注分错类别的样本点来进行拟合。
从上面的描述我们能提取出Adaboost模型的几个要点，即“误差”、“聚焦”。


首先需要构建误差表达式，在损失函数章节我们介绍过一种指数损失函数，这种损失函数特别适用于分类模型，可以量化错误的类别信息。
因此引入\cref{adazhishuhanshu}。其中$y$表示真实标签分类，$f(x)=\sum\limits_{m = 1}^M {{\alpha _m}{G_m}(x)}$，$G_m(x)$为基本分类器，${\alpha}_m$为基本分类器的权值。
\begin{align}\label{adazhishuhanshu}
L(y,f(x)) = exp[ - yf(x)]
\end{align}
这里有一个疑问，为什么使用$f(x)$而不是直接使用每一步迭代之后的最终分类器$G(x)$呢？对于“聚焦”的机制，Adaboost通过给每个样本添加权值来实现，预测对的样本权值小，预测错误的样本权值大。
又由于$f(x)=\sum\limits_{m = 1}^M {{\alpha _m}{G_m}(x)}$中每个基本分类器是一步一步迭代来的，因此对于第$m$个基本分类器$G_m(x)$，而$f_m(x)$又可以表示为\cref{adafmx}。
\begin{align}\label{adafmx}
{f_m}(x) = {f_{m - 1}} + {\alpha _m}{G_m}(x)
\end{align}

则，整个优化问题可以描述为下式，最终分类器为$G(x)=sign(f_m(x))$：
\begin{align}\label{adafmx}
({\alpha _m},{G_m}(x)) = arg{\rm{ }}\mathop {min}\limits_{\alpha ,G} \sum\limits_i^N {\exp [ - {y_i}({f_{m - 1}}({x_i}) + {\alpha}_m G_m({x_i}))]}
\end{align}
令${\bar w_{mi}} = \exp [ - {y_i}({f_{m - 1}}({x_i})]$，可以将上式简化为：
\begin{align}\label{adafmxjh}
({\alpha _m},{G_m}(x)) = arg\mathop {min}\limits_{\alpha ,G} \sum\limits_i^N {{{\bar w}_{mi}}\exp [ - {y_i}{\alpha}_m G_m({x_i})]}
\end{align}
为使上式最小化，可以分两步计算，类似于求偏导，将一个自变量视为常量，另一个自变量视为变量。首先将${\alpha}_m$视为常量，求使损失函数达到最小值时的$G_m(x)$,其中${\alpha}$大于$0$。
即\cref{adafmxjh}等价于下式:
\begin{align}
G_m^*(x) = arg\mathop {min}\limits_{{\alpha}_m ,G_m} \sum\limits_i^N {{{\bar w}_{mi}}\exp [ - {y_i}G_m({x_i})]}
\end{align}
由于${\bar w_{mi}}$也是常数,且值大于$0$，也可以进一步简化：
\begin{align}
G_m^*(x) = arg\mathop {min}\limits_{{\alpha}_m ,G_m} \sum\limits_i^N {\exp [ - {y_i}G_m({x_i})]}
\end{align}
将上式最小化就是将$\exp[-y_iG(x_i)]$最小化,这个式子可以作为基础分类器的损失函数,但是严格的推导现在还没有想明白,还有在回归情况的时候也未想明白,而基础分类器的损失函数的最小化是由基础分类器保证的。
再来讨论$\alpha$，由于$y$的值要么是1要么为-1，因此可以将\cref{adafmxjh}进一步推导：
\begin{align}
\begin{array}{l}
\sum\limits_i^N {{{\bar w}_{mi}}\exp [ - {y_i}\alpha G({x_i})]} \\
 = \sum\limits_{{y_i} = {G_m}({x_i})} {{{\bar w}_{mi}}{e^{ - \alpha }}}  + \sum\limits_{{y_i} \ne {G_m}({x_i})} {{{\bar w}_{mi}}{e^\alpha }} \\
 = \left( {{e^\alpha } - {e^{ - \alpha }}} \right)\sum\limits_{i = 1}^N {{{\bar w}_{mi}}I({y_i} \ne {G_m}({x_i}))}  + {e^{ - \alpha }}\sum\limits_{i = 1}^N {{{\bar w}_{mi}}} 
\end{array}
\end{align}

上式中${I({y_i} \ne {G_m}({x_i}))}$表示当$y_i$不等于$G_m(x_i)$时为1，两者相等时为0。然后将上式对$\alpha$求导得：
\begin{align}
\alpha _m^* = \frac{1}{2}\log \frac{{1 - {e_m}}}{{{e_m}}}
\end{align}
其中$e_m$为分类误差率:
\begin{align}
{e_m} = \frac{{\sum\limits_{i = 1}^N {{{\bar w}_{mi}}I({y_i} \ne {G_m}({x_i}))} }}{{\sum\limits_{i = 1}^N {{{\bar w}_{mi}}} }} = \sum\limits_{i = 1}^N {{w_{mi}}I({y_i} \ne {G_m}({x_i}))}
\end{align}
上式中${w_{mi}} = \frac{{{{\bar w}_{mi}}}}{{\sum\limits_{i = 1}^N {{{\bar w}_{mi}}} }}$，与$I(y_i \ne G_m(x_i))$相互作用，$I(y_i \ne G_m(x_i))$表示第$i$个样本产生的误差，$w_{mi}$的总和正好为1，因此我们可以直接
将$w_{mi}$这一项作为每个样本的权值，通过权值的大小来控制$I(y_i \ne G_m(x_i))$对损失函数的影响。此外使用$w_{mi}$作为权值的另一个好处的就是很容易得到其地推公式：
\begin{align}
{w_{mi}} = \frac{{{{\bar w}_{(m - 1)i}}\exp [ - {y_i}{\alpha _{(m - 1)}}{G_{(m - 1)}}({x_i})]}}{{\sum\limits_{i = 1}^N {{{\bar w}_{(m - 1)i}}\exp [ - {y_i}{\alpha _{(m - 1)}}{G_{(m - 1)}}({x_i})]} }}
\end{align}
\begin{tcblisting}{listing only,applelight,title={Adaboost伪码},
  listing options={basicstyle=\ttfamily,columns=fullflexible,
  language={[LaTeX]TeX},moretexcs={colorlet,definecolor,PassOptionsToPackage}}
}

 
    
\end{tcblisting}


\item 提升树\\
提升树是以分类树或者回归树为基本分类器的提升方法。
先从回归模型引入提升树的概念。设最终的提升树模型表示为：
\begin{align}
{f_M}(x) = \sum\limits_{m = 1}^M {T(x;{\Theta _m})}  = {f_{M - 1}}(x) + T(x;{\Theta _m})
\end{align}
$f_0(x)=0$，损失函数为：
\begin{align}
\sum\limits_{i = 1}^N {L({y_i},{f_{M - 1}}(x) + T({x_i};{\Theta _m}))}
\end{align}

通过最小化上述损失函数获取最优参数${\Theta}_m$，在预测实数连续值问题（回归模型）中，一般采用平方误差损失函数，则有：
\begin{align}\label{canchatishengshu}
\begin{array}{l}
L({y_i},{f_{M - 1}}(x) + T({x_i};{\Theta _m}))\\
 = {[{y_i} - {f_{M - 1}}(x) - T({x_i};{\Theta _m})]^2}\\
 = {[r - T({x_i};{\Theta _m})]^2}
\end{array}
\end{align}
上式中$r=y_i-f_{m-1}(x)$，并且可以看出此时只要构建基础分类器去拟合残差$r$就可以使损失函数达到最小。


以上就是提升树的理论基础。如果采用指数损失函数，也可以构建类似上式，如\cref{adafmx}描述的，可以将$-y_if_{m-1}(x_i)$看作为残差，用基础分类器$G(x_i)$去拟合这个残差。
现在我们将回归问题扩展到分类问题，在分类问题中我们经常采用对数损失函数，这种损失函数并不能显式的推导出\cref{canchatishengshu}的形式，如果想使用提升树的概念去构建模型，
首先需要解决“残差”表示这个问题。Freidman针对这一问题提出了梯度提升算法，利用损失函数的梯度值来近似表示“残差”，即可以表示为：
\begin{align}
- {\left[ {\frac{{\partial L(y,f({x_i}))}}{{\partial f({x_i})}}} \right]_{f(x) = {f_{m - 1}}(x)}}
\end{align}
用$c$表示真实的“残差”，根据拟合“残差”的要求，有$f_m(x_i)=f_{m-1}(x_i)+c$。现在我们构建了一个基础分类器采用的使梯度拟合的方式，因此在求得真实的“残差$c$”时，需要针对构造出来的树中的每一个叶子结点，
求出使损失函数最小的，也就是拟合叶子节点最好的输出值$c_{tj}$，在这一步求最优就是来弥补采用残差近似表示这种方法所带来的与真实残差的误差。即在每个叶子节点上进行使损失函数最小的计算。
好的回归树中的叶子结点都是较纯的样本集，在这里就代表，该叶子结点中样本对应的梯度值近似。然后再在当前叶子结点中使损失函数值达到最小。再通俗一点就是，先找个分类规则(基本分类器)将样本数据进行分类，
然后再在各分类数据集中使损失函数值达到最小。可以这样理解但是依旧不知道为什么进行这些计算？
\begin{align}
{c_{tj}} = \underbrace {\arg {\rm{ min}}}_c\sum\limits_{{x_i} \in {R_{tj}}} {L({y_i},{f_{t - 1}}({x_i}) + c)}
\end{align}
上式中$R_{mj}$表示第$j$个叶子节点，获取最优的“残差”表示之后，更新基本分类器：
\begin{align}
{f_m}(x) = {f_{m - 1}}(x) + \sum\limits_{j = 1}^J {{c_{mj}}I(x \in {R_{mj}})}
\end{align}
$J$表示叶子几点总的个数，$I(x \in R_{mj})$表示当样本属于叶子节点$R_{mj}$时为1，否则为0。模型的最终形式为：
\begin{align}
\hat f(x) = {f_M}(x) = \sum\limits_{m = 1}^M {\sum\limits_{j = 1}^J {{c_{mj}}I(x \in {R_{mj}})} }
\end{align}
其中$M$表示总共构建的基础分类器个数。
\end{enumerate}


提升算法的缺点就是模型的构建是串行的，因为下一个模型的构建依赖于上一个模型。

\section{EM算法}
期望最大算法（EM算法）是一种从不完全数据（存在隐含变量）中求解模型参数的最大似然估计或者最大后验概率估计方法。
EM算法有个前提是数据集的分布形态要提前知道，即参数可以未知，但是分布形态需要提前设定。
\subsection{一些准备概念}
在概率统计学的江湖存在着两大学派，一个是频率学派，一个是贝叶斯学派，该学派认为所有事件都是有先验概率的，最大后验概率就是该学派的理论表述。
\begin{enumerate}
\item 最大似然估计，MLE
\item 最大后验概率估计，MAP
\item 完全数据，不完全数据，Q函数
\end{enumerate}
最大似然估计与最大后验概率估计都是对参数的一种估计。在MLE中，是使似然函数
$P(x|\theta)$最大的时候参数$\theta$的值；而在MAP中，
则是求$\theta$使$P(x|\theta)P(\theta)$的值最大，这也就是要求$\theta$值不仅仅是让似然函数最大，同
时要求$\theta$本身出现的先验概率也得比较大。

\subsection{Q函数}
EM算法是一种算法，并不是一种模型，这种算法适用于解决不能通过解析式的方式求解最优解的情况。关键是构建Q函数，即完全数据对数似然函数对隐藏变量的期望。
假设：$(X_1,X_2,\cdots, X_n)$观测到的n个随机事件的结果，但是其中任意一个随机事件与隐藏变量$Z$有关系，$(Z_1,Z_2,\cdots, Z_n)$表示$n$个隐藏在$X$中的随机事件，完全数据的定义为：
$(X,Z)$，对完全数据构建对数似然函数有：
\begin{align}
log(P(X,Z | \theta))
\end{align}
式中$\theta$表示该概率分布的参数。由以上定义可以知Q函数的表达式为：
\begin{align}\label{Qfun}
Q(\theta,{\theta}^{(i)}) = E_z[logP(X,Z | \theta) | X,{\theta}^{(i)}] = \sum\limits_Z {logP(X,Z | \theta)P(Z | X, {\theta}^{(i)})}
\end{align}
上式表示第$i+1$次迭代时$Q$函数的表达式，${\theta}^{(i)}$表示第$i$次迭代$\theta$的估计，上式包含两个概率分布，一个是条件联合概率分布$P(X,Z | \theta)$，用于新一轮参数估计，只有$X$已知。
另外一个是条件概率分布$P(Z | X, {\theta}^{(i)})$，${\theta}^{(i)}$，$X$已知。从上式知，EM算法的前提是这两个概率分布的形态需要提前得知，比如符合高斯分布，其中$P(Z | X, {\theta}^{(i)})$为
$P(X,Z | \theta)$的边缘分布，所以只需给定$P(X,Z | \theta)$服从什么分布即可。混合高斯分布（GMM）就直接假设条件联合概率分布的分布形态为高斯分布，在下面章节会给出GMM模型更详细的介绍。
在得到Q函数的表示之后，就需要对Q函数进行极大化，来更新模型参数$\theta$。通过不断极大化Q函数来极大化完全数据的对数似然函数就是EM算法的核心思想。这一点Adaboost模型中也有使用，Adaboost是将真实的损失函数小于等于指数损失函数，
然后不断减小指数损失函数来最小化真实的损失函数。总结一下就是当我们不能很方便的优化某一函数时，我们可以适当的放大或者缩小函数来构建出一个我们熟悉的函数，然后通过优化这一熟悉函数来最优化原始函数。
关于极大化Q函数等价于极大化完全数据对数似然函数是由Jensen不等式保证的，Jensen不等式可以简单表示为：
\begin{align}
F(E(x)) \ge E(F(x))
\end{align}
其中，$E(x)$表示自变量$x$的期望，$F$表示一个单调增函数，对于怎样使用Jensen不等式导出对数似然函数的下限请参考《统计学习方法》一书。

\subsection{高斯混合模型}
高斯混合模型是EM算法的一种应用，上一节中已经提到这个模型简单的假设Q函数中的条件联合分布为高斯分布，你也可以将条件联合分布假设为贝塔分布或者其他分布，来构建你自己的混合模型，
当然前提是能对Q函数进行极大值求解。下面我们给出高斯混合模型的定义：
\begin{align}
P(y|\theta) = \sum\limits_{k=1}^K {{\alpha}_k{\phi}(y|{\theta}_k)}
\end{align}
其中，${\alpha}_k$是系数，${\alpha}_k \ge 0, \sum\limits_{k=1}^K{{\alpha}_k}=1$，相当于Q函数中的条件概率$P(Z | X, {\theta}^{(i)})$。$\phi(y|{\theta}_k)$是高斯分布密度函数，${\theta}_k=({\mu}_k,{\sigma}_k^2)$，
即第$k$个模型的参数。高斯混合模型是生成模型，观测数据$(y_1,y_2,y_3,\dot,y_n)$是以概率${\alpha}_k$选择分高斯分布，然后再以高斯分布来生成的。这是前提，因此完全数据为观测数据加上生成观测数据的高斯分布是那个，
表示为${\gamma}_{jk}$，${\gamma}_{jk}$只在第$j$个观测来自第$k$个高斯分布时为$1$，其余为$0$。完全数据表示为$(y_i,{\gamma}_{j1},{\gamma}_{j2},{\gamma}_{j3},\dot,{\gamma}_{jn})$。
有了以上定义，很容易可以给出高斯混合模型的Q函数，首先给出完全数据的对数似然函数：
\begin{align}
\log P(y,\gamma |\theta ) = \sum\limits_{k = 1}^K {{n_k}\log {\alpha _k}}  + \sum\limits_{j = 1}^N {{\gamma _{jk}}\left[ {\log \left( {\frac{1}{{\sqrt {2\pi } }}} \right) - \log {\sigma _k} - \frac{1}{{2\sigma _k^2}}{{\left( {{y_j} - {\mu _k}} \right)}^2}} \right]}
\end{align}
关于上式的推到见图\ref{GMM1}\ref{GMM2}\ref{GMM3}。
\begin{figure}
  \centering
  \includegraphics[width=.8\textwidth]{GMM1.png} 
  \caption{GMM Q函数推导1}
  \label{GMM1} 
\end{figure}

\begin{figure}
  \centering
  \includegraphics[width=.8\textwidth]{GMM2.png} 
  \caption{GMM Q函数推导2}
  \label{GMM2} 
\end{figure}

\begin{figure}
  \centering
  \includegraphics[width=.5\textwidth]{GMM3.png} 
  \caption{GMM Q函数推导3}
  \label{GMM3} 
\end{figure}

其次再对对数似然函数求期望既得Q函数：
\begin{align}
Q(\theta ,{\theta ^{(i)}}) = E\left\{ {\sum\limits_{k = 1}^K {{n_k}log{\alpha _k}}  + \sum\limits_{j = 1}^N {{\gamma _{jk}}\left[ {\log \left( {\frac{1}{{\sqrt {2\pi } }}} \right) - \log {\sigma _k} - \frac{1}{{2\sigma _k^2}}{{\left( {{y_j} - {\mu _k}} \right)}^2}} \right]} } \right\}
\end{align}

求得Q函数之后再进行极大化操作，就可以更新每个高斯分布的参数，以及参数${\alpha}_k$了，这里直接给出更新公式：
\begin{align}
\begin{array}{l}
{{\hat \mu }_k} = \frac{{\sum\limits_{j = 1}^N {{{\hat \gamma }_{jk}}{y_j}} }}{{\sum\limits_{j = 1}^N {{{\hat \gamma }_{jk}}} }},k = 1,2, \cdots ,K\\
\hat \sigma _k^2 = \frac{{\sum\limits_{j = 1}^N {{{\hat \gamma }_{jk}}{{\left( {{y_j} - {\mu _k}} \right)}^2}} }}{{\sum\limits_{j = 1}^N {{{\hat \gamma }_{jk}}} }},k = 1,2, \cdots ,K\\
{{\hat \alpha }_k} = \frac{{{n_k}}}{N} = \frac{{\sum\limits_{j = 1}^N {{{\hat \gamma }_{jk}}} }}{N},k = 1,2, \cdots ,K
\end{array}
\end{align}


\chapter{聚类模型}
聚类模型一般在数据预处理阶段使用，比较常用的聚类模型有，K-Means，谱聚类，密度聚类，层次聚类等
\section{隐马尔可夫模型}
隐马尔可夫模型主要用于标注问题，并且可以通过标注的信息完成分类任务；比如语音识别问题，模型接受的是一串语音信号，返回的是一句话，这句话中的每一个字可以看成语音信号中某一片段的标注。

\subsection{一些定义}
隐马尔可夫模型 （HMM）是关于时序的概率模型，描述由一个马尔可夫链随机生成不可观测的状态随机序列，再由各个状态生成一个观测随机序列的过程。


其中马尔可夫链（一阶）简单来说是指在一个时间序列中，这一时刻的状态只与上一时刻的状态相关。马尔可夫链随机生成不可观测的状态随机序列称为状态序列；
由这个状态序列中的每个状态生成的一个由观测值组成的序列称为观测序列。由以上定义可以抽象出数学概念：
\begin{align}
\begin{array}{l}
Q = \{ {q_1},{q_2}, \cdots ,{q_N}\} ,V = \{ {v_1},{v_2}, \cdots ,{v_M}\} \\
I = \{ {i_1},{i_2}, \cdots ,{i_T}\} ,O = \{ {o_1},{o_2}, \cdots ,{o_T}\} 
\end{array}
\end{align}
其中$N$，$M$分别表示可能的隐藏状态数，即总共有几种隐藏状态；几种观测状态；I为一次测试中长度为T的状态序列，O是其对应的观测序列。
其中状态序列符合一阶马尔可夫性质，即存在一个状态转移矩阵：
\begin{align}
A=[a_{ij}]_{N*N}
\end{align}
其中，
\begin{align}
a_{ij}=P(i_{t+1}=q_j | i_{t}=q_i), i,j=1,2,\cdots,N
\end{align}
是在时刻$t$处于状态$q_i$的条件下在时刻$t+1$转移到状态$q_j$的概率。


B是观测概率矩阵，即由隐藏状态到观测状态的转换概率组成的矩阵。
\begin{align}
B=[b_j(k)]_{N*M}
\end{align}
其中,
\begin{align}
b_j(k) =P(o_t=v_k|i_t=q_j),k=1,2,\cdots,M;j=1,2,\cdots,N
\end{align}
是在时刻$t$处于状态$q_j$的条件下生成观测$v_k$的概率。
对于初始时刻，因为没有上一个状态，因此需要提供一个初始状态概率向量：
\begin{align}
\pi = ({\pi}_i)
\end{align}
其中，
\begin{align}
{\pi}_i = P(i_1=q_i),i=1,2,\cdots,N
\end{align}
是时刻$t=1$处于状态$q_i$的概率。
由以上定义，一个隐马尔可夫模型由参数$A,B,\pi$唯一确定。


\subsection{三个问题}
对于一个可使用隐马尔可夫模型解决的问题，一般都具有三个部分：模型参数($A,B,\pi$)，观测序列，隐藏序列。三个部分对应三个问题：


已知模型参数和观测序列，计算在模型参数的条件下当前观测序列出现的概率$P(O|\lambda)$，即概率计算问题。


已知观测序列，估计模型参数，即学习问题。根据是否提供隐藏序列（可以理解为标注）又分为监督问题和非监督问题，其中非监督问题即为EM算法。监督算法中一般用频数近似频率。


已知观测序列，模型参数，估计使观测序列条件概率最大$P(I|O)$的隐藏状态序列（标注），即预测问题吗，维特比算法用于解决这一问题。

\begin{figure}
  \centering
  \includegraphics[width=.9\textwidth]{HMM1.png} 
  \caption{HMM 概率计算示意图}
  \label{HMM1}
\end{figure}
针对概率计算问题又分为前向概率计算和后向概率计算，关于采用前向概率计算和后向概率计算所减少的运算量还没有理解，需要再讨论：


如图\ref{HMM1}所示，从神秘领域到$t_1$时刻用初值表示，即初始概率${\pi}_i$乘以观测序列转移概率：
\begin{align}
a_1{i}={\pi}_ib_i{o_i},i=1,2,\cdots,N
\end{align}
在求$t_2$时刻时我们假设$t_2$时刻的状态是$i_1$如图中蓝线所示，因为不确定是从$t_1$的那个状态转换过来的，因此需要考虑所有情况，即对单一情况求和，这里的单一情况是指：
\begin{align}
{\alpha}_t(j)a_{ji}
\end{align}
表示从$t$时刻的$j$状态转换为$t+1$时刻的$i$状态，单一情况其实表示的是条件概率，条件就是$t$时刻状态为$j$，要想去除这一条件就是考虑所有情况然后求和，即：
\begin{align}
\sum\limits_{j = 1}^N {{\alpha _t}(j){a_{ji}}}
\end{align}
上式中${\alpha _t}(j)$表示$t$时刻的前向概率，上式表示了从$t$时刻到$t+1$时刻状态为$i$的概率。由以上公式可以写出考虑到观测概率的递推公式：
\begin{align}
{\alpha _{t + 1}}(i) = \left[ {\sum\limits_{j = 1}^N {{\alpha _t}(j){a_{ji}}} } \right]{b_i}({o_{t + 1}}),i = 1,2, \cdots ,N
\end{align}
对于观测序列$O = \{ {o_1},{o_2}, \cdots ,{o_T}\} $，有前向概率表达式：
\begin{align}
P({o_1},{o_2}, \cdots ,{o_T}, i_T=i, | \lambda) = {\alpha}_T(i)
\end{align}
我们要求的是$P(O|\lambda)$，与上式对比少一个条件$i_T=i$，上面提到过要想排除条件只要对所有情况求和即可，即：
\begin{align}
P(O|\lambda) = \sum\limits_{j = 1}^N{{\alpha}_T(i)}
\end{align}
对于后向概率$P({o_t},{o_{t+1}}, \cdots ,{o_T}, i_t=i, | \lambda) = {\beta}_t(i)$采用同样的方式即可获取，参照图\ref{HMM1}中绿色路径。前向概率是要想到达当前状态，有N条路径；后向概率是，从当前状态出发，有N条路径可选。


对于学习算法问题无监督模型参考参见EM算法讲解，监督模型一般通过统计估计模型参数，可以根据已标注数据集计算频率。


第三类问题在实际中经常用到，即求最大概率隐藏状态序列问题，主要以介绍维特比算法为主。
维特比算法是一种动态规划算法，动态规划算法的特点是可以将问题分为几个阶段，通过求解几个阶段的最优解组合为整个问题的最优解。
假设有$N$个状态$t_1,t_2,\cdots,t_N$，现在要求从$t_1$时刻到$t_N$时刻的最优路线，对于这个问题，可以将其分解为多个阶段，比如：
从$t_1$到$t_2$，$t_2$到$t_3$等，能进行这样分解是建立在下面这个原理之上：

假设总的最优路径经过$t_i$时刻的状态$i$这个点，那么总的最优路径一定包含从$t_1$到$t_i$时刻的最优路径。基于这个原理可以将维特比算法描述如下,
首先引入几个定义：
\begin{align}
{\delta}_t(i)=\underbrace{max}_{i_1,i_2,\cdots,i_{t-1}}P(i_t=i,i_1,i_2,\cdots,i_{t-1},o_t,\cdots,o_1 | {\lambda})
\end{align}
上式表示时刻$t$状态为$i$的所有的从$i_1$到$i_t$单个路径中概率最大值。为了表示路径，需要定义最优路径上的节点。
\begin{align}
{\Phi}_t(i)=arg \underbrace{max}_{1{\le}j{\le}N}[{\delta}_{t-1}(j)a_{ji}]
\end{align}
${\Phi}_t(i)$就表示最优路径上上个时刻是从那个状态到当前状态的。下面定义维特比算法的计算步骤：


第一步：给定模型参数$\lambda$,观测序列。


第二步：由初始概率确定初始时刻概率：
\begin{equation}
\begin{split}
&{\delta}_1(i)={{\pi}_i}b_{i}(o_1) \\
&{\Phi}_1(i)=0 \\
\end{split}
\end{equation}
第三步：递推求出从时刻$1$到$T$：
\begin{equation}
\begin{split}
&{\delta}_T(i)=\underbrace{max}_{1{\le}j{\le}N} [{\delta}_{T-1}(j)a_{ji}]b_i(o_T)\\
& {\Phi}_T(i)=arg \underbrace{max}_{1{\le}j{\le}N} [{\delta}_{T-1}(j)a_{ji}]\\
\end{split}
\end{equation}
第四步：回溯求出最优路径，做为该样本的标签，可以根据最优路径进行聚类，或者用这个标签与数据库中的数据进行匹配实现识别。

\subsection{条件随机场}
首先条件随机场(CRF)是序列化的逻辑回归，讲述CRF以下图为例。

\begin{figure}
  \centering
  \includegraphics[width=.8\textwidth]{CRF01.png} 
  \caption{CRF解释1}
  \label{CRF01}
\end{figure}
\begin{figure}
  \centering
  \includegraphics[width=.8\textwidth]{CRF02.png} 
  \caption{CRF解释2}
  \label{CRF02}
\end{figure}
\begin{figure}
  \centering
  \includegraphics[width=.8\textwidth]{CRF03.png} 
  \caption{CRF解释3}
  \label{CRF03}
\end{figure}

CRF与HMM的区别：
\begin{enumerate}
\item CRF可以定义数量更多，种类更丰富的特征函数。HMM模型具有天然具有局部性，就是说，在HMM模型中，当前的单词只依赖于当前的标签，当前的标签只依赖于前一个标签。
\item 这样的局部性限制了HMM只能定义相应类型的特征函数，我们在上面也看到了。但是CRF却可以着眼于整个句子s定义更具有全局性的特征函数。
\item CRF可以使用任意的权重，将对数HMM模型看做CRF时，特征函数的权重由于是log形式的概率，所以都是小于等于0的，而且概率还要满足相应的限制，但在CRF中，每个特征函数的权重可以是任意值，没有这些限制。
\end{enumerate}

\section{贝叶斯模型}

考虑一个根据已有数据集预测下一个数据的问题。数学语言描述为：


假设$D=(x_1,x_2,\cdots,x_n)$是一个数据集，有$N$个特征$(a_1,a_2,\cdots,a_N)$，即特征向量，其中$a_1$取值有$(a_{11},a_{12},\cdots,a_{J_1})$，$a_2$取值有$(a_{21},a_{22},\cdots,a_{2J_2})$。
现在要预测一个新的数据$x_{n+1}$。


对于这个问题，我们保守的做法就是求已有数据集的期望，拿期望值作为预测值。即：
\begin{align}\label{qiwangbyes}
E(x_{n+1})= \sum_{i=1}^N{\sum_{J_1,J_2,\cdots,J_N}{a_{iJ_*}p(a_{iJ_*}|D)}}
\end{align}
上式中$J_*$表示可取$(J_1,J_2,\cdots,J_N)$。$p(a_{iJ_*}|D)$为通过统计样本集$D$获得的第$i$个特征取值为$J_*$时的频率。


对于经典频率学派，他们认为某一特征取某一个值的概率是固定的，因此对于这一问题，能很快的给出预测；但是对于贝叶斯学派而言，他们认为某一特征取某一个值的概率是一个随机变量，
并且用服从一定的分布，通过先验概率这个概念定义这个分布$p[X=p(a_{iJ_*}|D)]$，并假设这个分布的参数为$\theta$。则\cref{qiwangbyes}在贝叶斯学派的理论中定义为：
\begin{align}\label{qiwangbyes2}
E(x_{n+1})= \sum_{i=1}^N{\sum_{J_1,J_2,\cdots,J_N}{a_{iJ_*}\int_{\theta}{p(a_{iJ_*},{\theta}|D)d{\theta}}}}
\end{align}
求积分即求边缘概率。上式的关键是求解$\int_{\theta}{p(a_{iJ_*},{\theta}|D)}d{\theta}$，利用条件概率公式得：
\begin{align}
p(a_{iJ_*},{\theta}|D)=p(a_{iJ_*}|{\theta},D)p({\theta}|D)
\end{align}
上式中$p(a_{iJ_*}|{\theta},D)$，$D$对于$a_{iJ_*}$的影响是通过${\theta}$对$a_{iJ_*}$的影响来体现的，所以$p(a_{iJ_*}|{\theta},D)$可以简化为：
$p(a_{iJ_*}|{\theta})$，\cref{qiwangbyes2}同样可以简化为：
\begin{align}\label{qiwangbyes2}
E(x_{n+1})= \sum_{i=1}^N{\sum_{J_1,J_2,\cdots,J_N}{a_{iJ_*}\int_{\theta}{p(a_{iJ_*}|{\theta},D)p({\theta}|D)d{\theta}}}}
\end{align}
上式即为贝叶斯学派对于此问题的解决方式，式子中存在一个积分，如果概率值取值${\theta}$较少的话，还可以通过求和直接进行计算，但是如果概率值是连续的，求这个积分式将是复杂的，
即便求得解析的积分式，将$\theta$的所有情况都代入求解也需要大量的计算量（这句话有待讨论），因此为了降低复杂度，直接找到一个真实值的近似，即只考虑一种情况，后验概率取极大值的情况下的
$\theta$值（MAP算法）。在确定了$\theta$之后就可以计算出期望值，再用期望值作为预测值。


现在将贝叶斯学派的观点应用于分类问题，假设有待分类项$B=(b_1,b_2,\cdots,b_N)$，应用贝叶斯后验概率的理论进行分类(思考：使用频率学派的观点能否完成分类任务)。
设有$K$个类别$c_1,c_2,\cdots,c_K$，通过计算$p(c_j|b_1,b_2,\cdots,b_N),j=1.\cdots,K$最大值，以最大值对应的$c_j$作为待分类项的分类标签。由贝叶斯公式得：
\begin{align}
p({c_j}|{b_1},{b_2}, \cdots ,{b_N}) = \frac{{p({b_1},{b_2}, \cdots ,{b_N}|{c_j})p({c_j})}}{{p({b_1},{b_2}, \cdots ,{b_N})}}
\end{align}
对于上式中的${p({b_1},{b_2}, \cdots ,{b_N}|{c_j})}$，直接令其等于$p({b_1}|{c_j})p({b_2}|{c_j}) \cdots p({b_N}|{c_j})$，由于这个假设很“朴素”，所以为“朴素贝叶斯”。
对于公式中概率值的计算，直接通过已知标签的训练集中进行统计获取，即拿频率做概率（这一点又是频率学派的观点），但是《统计学习方法》一书中乘这一步为极大似然估计和贝叶斯估计，这个解释不是很理解。
有公式：
\begin{align}
\begin{array}{l}
P({c_j} = {c_k}) = \frac{{\sum\limits_{i = 1}^N {I({c_j} = {c_k})} }}{N},{\rm{ k = 1,2,}} \cdots {\rm{,K}}\\
{\rm{P(}}{{\rm{b}}_1}{\rm{|}}{{\rm{c}}_j} = {c_k}{\rm{) = }}\frac{{\sum\limits_{i = 1}^N {I({c_j} = {c_k},{b_1})} }}{{\sum\limits_{i = 1}^N {I({c_j} = {c_k})} }}
\end{array}
\end{align}
针对概率${\rm{P(}}{{\rm{b}}_1}{\rm{|}}{{\rm{c}}_j} = {c_k}{\rm{)}}$的计算，由几个推广，当为特征属性值为连续值，且服从高斯分布时，可以构建高斯贝叶斯；同样也可以构建伯努利贝叶斯和多项式贝叶斯。


对于“朴素”的假设，在应用场景中大多是不满足这一假设的，当样本特征属性之间有关联时，上述模型显然不能满足条件，因此需要对上述模型进行推广，即贝叶斯网络模型。
我们以一个例子来讲述贝叶斯网络模型的概念：


例：有一天早晨，拉比克离开他的房子的时候发现他家花园中的草地是湿的，有两种
可能，第一：昨天晚上下雨了，第二：他昨天晚上忘记关掉花园中的喷水器，接
下来，他观察他的邻居米拉娜，发现她家花园中的草地也是湿的，因此，他推断，
他家的草地湿了是因为昨天晚上下雨的缘故。从这个例子中抽象出如图\ref{beiyesiwangluo}所示的简单网络，以及概率值。
\begin{figure}
  \centering
  \includegraphics[width=.6\textwidth]{beiyesiwangluo.png} 
  \caption{示例概率值及网络关系示意}
  \label{beiyesiwangluo}
\end{figure}
图\ref{beiyesiwangluo}中$R$表示下雨，$S$表示忘记关掉花园中的喷水器，L表示拉比克家的草地是湿的，M表示米拉娜家的草地是湿的。
因此问题符号化为：$max\{p(S=1|L=1,M=1),p(R=1|L=1,M=1)\}$。至于为什么成这个图模型为贝叶斯网络，我认为是计算这两个概率的时候使用了贝叶斯公式。
对于公式$p(S=1|L=1,M=1)$应用贝叶斯公式有：
\begin{align}
p(S=1|L=1,M=1)=\frac{p(L=1,M=1|S=1)p(S=1)}{p(L=1,M=1)}
\end{align}
为了计算上式中的$p(L=1,M=1|S=1)$和$p(L=1,M=1)$，这两个概率都为边缘概率，边缘概率可以通过求和来计算即：
\begin{align}
\begin{array}{l}
p(L = 1,M = 1|S = 1) = \sum\limits_R {p(L = 1,M = 1|S = 1,R)} \\
{\rm{p(L = 1,M = 1) = }}\sum\limits_{R,S} {{\rm{p(L = 1,M = 1|}}R,S{\rm{)}}} 
\end{array}
\end{align}
当$R$确定时，$L$与$M$为独立事件，贝叶斯网络中独立事件的判断由图给出。
\begin{align}
\begin{array}{l}
{\rm{p(L  =  1,M  =  1|S  =  1,R)  =  p(R)p(L = 1|S  =  1,R)p(M = 1|S  =  1,R)}}\\
{\rm{                                       = p(R)p(L = 1|S  =  1,R)p(M = 1|R)}}
\end{array}
\end{align}
经过上面的整理并计算可以求出$p(S=1|L=1,M=1)=0.1604, p(R=1|L=1,M=1)=0.9328$，因此判断是下雨导致的草地变湿。

\begin{framed}
题外小记：贝叶斯网络的应用应该很广泛的，理论知识也是很广的，此处写的几点是很少的，很不完善的，但是目前我所理解的就这么多，剩下的以后等理解了再补吧。


奥坎姆剃刀：如非必需，勿增实体


(More things should not be used than are necessary)


换句话说，如果关于一个或多个现象，有许多种理论都能作出同样准确的解释，那么应该挑选其中使用假定最少的。
如果我们现在再看爱因斯坦说的那句话：


Everything should be made as simple as possible, but not simpler。


你就会认识到，as simple as possible，就是先验概率越大的原因越好；而 not simpler，就是说这个原因仍然需要能够解释当前的观测。这句话翻译成贝叶斯定理的语言，就是说，你最终找到的原因是在能够解释当前的观测的前提下，先验概率最大的那个原因。
所以我们可以说，奥卡姆剃刀，是贝叶斯定理的一种特殊情况。奥卡姆剃刀告诉我们，在多个有相同的解释力的原因中要选出一个简单的；而贝叶斯定理告诉我们更一般的情况，即在解释力和复杂性中找到最好的平衡。

\end{framed}


\section{主题模型}

在自然语言处理中，关键词就是主题词，两者是等价的。提取一个文本的关键词的算法有:TF-IDF算法、TextRank算法\cite{Mihalcea2004TextRank}、LSA、LSI、pLSA、LDA。本章节主要介绍
LSA、pLSA、LDA。
\subsection{LSA}
LSA模型，浅层语义分析模型，个人感觉这个模型比较牵强，模型使用奇异值分解正好把一个矩阵分为三个矩阵相乘，而这三个矩阵的维度又正好可以解释词的个数、文档的个数，因此就直接那这三个矩阵作为词-词类矩阵和文档类-文档矩阵。
这样做法总感觉没有依据，只是恰好奇异值分解\cite{Dan1996A}有这种形式，如果按照这种思路，LSA模型应该主要将的是升维，只是奇异值分解正好可以作为升维的方式，将一个矩阵映射为三个矩阵，这也是称这个模型为“浅层”的原因。
同时这也是一种挖掘潜在信息的一种思想。

考虑一个文档集合，经过分词，停用词处理之后，可以获得一个词-文档矩阵$X$，经过奇异值(SVD)分解之后，得到三个矩阵$U,D,V^T$。如图所示。
其中$U$的列数少于$X$列数的原因是利用到SVD的一个性质：

对于奇异值,它跟我们特征分解中的特征值类似，在奇异值矩阵中也是按照从大到小排列，而且奇异值的减少特别的快，在很多情况下，前10\%甚至1\%的奇异值的和就占了全部的奇异值之和的99\%以上的比例。也就是说，我们也可以用最大的k个的奇异值和对应的左右奇异向量来近似描述矩阵。
奇异值分解也可以用于降维中。图中$U$为词-词类矩阵，每一行表示当前词在各个词类中的重要程度；$V^T$为文档类-文档矩阵，每一列表示各中文档类在每一份文档中的重要程度。
得到了文档类-文档矩阵，就可以以该矩阵中的每一列为输入进行聚类，处理文档相似问题；或者对词-词类矩阵中的每一列进行聚类，处理一义多词问题。


从上面的介绍可以总结出LSA的优缺点：

\begin{enumerate}
\item 与语言无关，模型的输入时词-文档矩阵。
\item 充分利用了冗余数据，因为降维去除了部分噪声。
\item 并不能解决一词多义问题。
\item SVD计算比较复杂，对于新来的一份文档，需要重新进行奇异值分解，才能完成文本分类。
\end{enumerate}
为什么只能处理一义多词，而不能处理一词多义呢？因为一义就相当于一个聚类，而一个词在浅层语义空间只对应一个点。

\subsection{pLSA}
LSA模型不是基于概率的，pLSA在LSA的基础上引入了概率，并阐述了一篇文档中词的产生方法。LSA中我们有两个矩阵词-词类矩阵和文档类-文档矩阵，在此基础上考虑一篇文档是怎样生成的，
要写一篇文章，这篇文章的主题是关于什么的，然后再遣词造句。可以从这句话中提取出三个概率：文档概率$p(d_i)$，我对这个概率的理解是，全世界有个文档集，你以一定的概率被指定写一类文档，这个解释还是很牵强还需要继续思考；
文档确定之后的主题概率$p(z_k|d_i)$且服从多项式分布，主题确定后的词概率$p(w_j|z_k)$，服从多项式分布。这三个概率公式中$w_j,d_i$是显式变量，$z_k$为隐变量。因此这个问题就变成寻找两个多项式分布参数的问题，又因为包含隐变量$z_k$
因此可以选用EM算法进行求解，关于EM算法请参照EM算法章节，这里不再过多介绍只给出似然函数：
\begin{align}
L = \prod\limits_m^M {\prod\limits_n^N p } ({d_m},{w_n}) = \prod\limits_m^{M'} {\prod\limits_n^{N'} p } {({d_m},{w_n})^{n({d_m},{w_n})}}
\end{align}
式中$M'$,$N'$表示合并重复词之后的计数，$n(d_m,w_n)$表示$d_m$文档中含有几个$w_n$词。

\subsection{LDA}
对于包含隐藏变量的联合分布，一般有两种方法求解，一种是使用EM算法，另外一种就是采用Gibbs采样统计。隐含狄利克雷模型(LDA)模型就是采用Gibbs采样来计算隐藏变量的联合分布的。
关于LDA详细的理论证明，《LDA数学八卦》一文已给出，题外话：该篇文档，开始的几篇介绍的很细致，作者花费时间去追根溯源是很难得的，但是后面几张，作者的论述就有点力不从心了，
特别是数学公式的书写，没有给出每个公式中字符的意思，这样给理解造成了困难，不过作者标题为“八卦”也就无可厚非了，本章节主要给出LDA模型中几个重要的知识点。
假设语料库中有$M$篇文档，定义词矩阵:
\begin{align}
\left[ {{w_{ij}}} \right] = \left[ {\begin{array}{*{20}{c}}
{{{\vec w}_1}}\\
{{{\vec w}_2}}\\
 \vdots \\
{{{\vec w}_M}}
\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}
{{w_{11}}}&{{w_{12}}}& \cdots &{{w_{1n}}}\\
{{w_{21}}}&{{w_{22}}}& \cdots &{{w_{2n}}}\\
 \vdots & \vdots & \ddots & \vdots \\
{{w_{M1}}}&{{w_{M2}}}& \cdots &{{w_{Mn}}}
\end{array}} \right]
\end{align}
上式中$n$为主题个数，每一行表示一个文档中的词分布，每一列与主题对应。对应的主题矩阵为：
\begin{align}
\left[ {{z_{ij}}} \right] = \left[ {\begin{array}{*{20}{c}}
{{{\vec z}_1}}\\
{{{\vec z}_2}}\\
 \vdots \\
{{{\vec z}_M}}
\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}
{{z_{11}}}&{{z_{12}}}& \cdots &{{z_{1n}}}\\
{{z_{21}}}&{{z_{22}}}& \cdots &{{z_{2n}}}\\
 \vdots & \vdots & \ddots & \vdots \\
{{z_{M1}}}&{{z_{M2}}}& \cdots &{{z_{Mn}}}
\end{array}} \right]
\end{align}
主题矩阵与词矩阵一一对应。


狄利克雷分布，其概率密度函数描述为：


对独立同分布的连续随机变量$X \in R_d$和支撑集$X \in (0,1), ||X||=1$，若$X$服从狄利克雷分布，则其概率密度函数Dir(X|\alpha)有如下定义：
\begin{align}\label{dilikelei}
\begin{array}{l}
D(X|\alpha ) = \frac{1}{{B(\alpha )}}\prod\limits_{i = 1}^d {X_i^{{\alpha _i} - 1}} \\
B(\alpha ) = \frac{{\prod\nolimits_{i = 1}^d {\Gamma ({\alpha _i})} }}{{\Gamma ({\alpha _0})}},{\alpha _0} = \sum\limits_{i = 1}^d {{\alpha _i}} ,d \ge 3
\end{array}
\end{align}
其中，$\alpha  \in \{ {\alpha _1}, \cdots ,{\alpha _d}\}  > 0$是无量纲的分布参数，${\alpha}_0$是分布参数的和，$B({\alpha})$是多元Beta函数，
$\Gamma({\alpha})$为Gamma函数。


多项式分布，其概率密度函数为：
\begin{align}\label{duoxiangshi}
p({x_{{n_1}}}, \cdots {x_{{n_k}}}) = \frac{{n!}}{{{n_1}! \cdots {n_k}!}}p_1^{{n_1}} \cdots p_k^{{n_k}},\sum\limits_{i = 1}^k {{n_i} = n}
\end{align}


LDA模型中文档对于主题模型的分布为多项式分布，而多项式分步中的参数，如\cref{duoxiangshi}中的$(p_1, \cdots p_k)$，也服从一个分布，称为先验分布，
并以狄利克雷分布为先验分布，即有狄利克雷分布生成概率值$(p_1, \cdots p_k)$，然后再使用多项式分布生成样本$(z_1,\cdots,z_n)$；相应的主题词分布也是
多项式分布，也具有上述形式的推导。假设两个先验分布的参数为：$\alpha  \in \{ {\alpha _1}, \cdots ,{\alpha _{d_m}}\}, \beta  \in \{ {\beta _1}, \cdots ,{\beta _{d_w}}\}$，
其中$d_m$为文档数，$d_w$为主题的个数。


现在计算词-主题的联合分布概率$p(w,z)$，采用Gibbs采样方法。采样过程中需要已知条件概率p(z|w)，然后依据这个条件概率进行采样。
Gibbs采样算法以及LDA模型训练过程：
\begin{enumerate}
\item 随机给每份文档中的每个词赋一个主题
\item 因为Gibbs采样必须沿着坐标轴变换，依次选择每份文档中的一个词，统计去掉这个词之后统计量（笼统的描述，具体参见下面伪码，统计量为什么需要详细描述）。
\item 用统计量计算条件概率$p(z|w)$值，以这个概率值构建多项式分布采样出下一个主题赋值给被选中的词，依上面顺序进行采样直到采样收敛(怎样判断收敛还需要讨论，不过程序中一般采用迭代步骤来控制循环)。
\item 当采样收敛时，统计出主题-词矩阵，该矩阵就是LDA模型。
\end{enumerate}
上述步骤中统计出了一个主题-词矩阵，LSA模型中也有一个词-词类矩阵，不知道这两个矩阵之间有什么联系以及为什么LDA就可以处理一词多义？这个需要进一步的思考。
\begin{tcblisting}{listing only,applelight,title={Gibbs采样函数},
  listing options={basicstyle=\ttfamily,columns=fullflexible,
  language={[LaTeX]TeX},moretexcs={colorlet,definecolor,PassOptionsToPackage}}
}

def sampling(self,i,j):  
    #换主题  
    topic = self.Z[i][j]  
    #只是单词的编号，都是从0开始word就是等于j  
    word = self.dpre.docs[i].words[j]  
    #if word==j:  
    #    print 'true'  
    self.nw[word][topic] -= 1  
    self.nd[i][topic] -= 1  
    self.nwsum[topic] -= 1  
    self.ndsum[i] -= 1  
    
    Vbeta = self.dpre.words_count * self.beta  
    Kalpha = self.K * self.alpha  
    self.p = (self.nw[word] + self.beta)/(self.nwsum + Vbeta) * \  
            (self.nd[i] + self.alpha) / (self.ndsum[i] + Kalpha)  
    
    #随机更新主题的吗  
    # for k in xrange(1,self.K):  
    #     self.p[k] += self.p[k-1]  
    # u = random.uniform(0,self.p[self.K-1])  
    # for topic in xrange(self.K):  
    #     if self.p[topic]>u:  
    #         break  
    
    #按这个更新主题更好理解，这个效果还不错 
    #这一点还为理解为什么采用多项式分布    
    p = np.squeeze(np.asarray(self.p/np.sum(self.p)))  
    topic = np.argmax(np.random.multinomial(1, p))  
    
    self.nw[word][topic] +=1  
    self.nwsum[topic] +=1  
    self.nd[i][topic] +=1  
    self.ndsum[i] +=1  
    return topic 
    
\end{tcblisting}










































拓展1：在线训练的条件

%============================================================
\bibliographystyle{plain}
\bibliography{refdoc}
\end{document}
